public class BinarySearchTree {
 
    static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
 
        TreeNode(int key) {
            this.val = key;
        }
    }
 
    public TreeNode root;

    public boolean insert(int key) {
        TreeNode Node=new TreeNode(key);
        if(root==null){
            root=Node;
            return true;
        }
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null){
            if(cur.val==key){
                return false;
            }else if(cur.val>key){
                prev=cur;
                cur=cur.left;
            }else{
                prev=cur;
                cur=cur.right;
            }
        }
        if(key>prev.val){
            prev.right=Node;
        }else{
            prev.left=Node;
        }
        return true;
    }
    public TreeNode search(int key) {
      TreeNode cur=root;
      while(cur!=null){
          if(cur.val==key){
              return cur;
          }else if(cur.val>key){
              cur=cur.left;
          }else{
              cur=cur.right;
          }
      }
        return null;
    }
    public boolean remove(int key) {
       TreeNode cur=root;
       TreeNode prev=null;
       while(cur!=null){
           if(cur.val==key){
               break;
           }else if(cur.val>key){
               prev=cur;
               cur=cur.left;
           }else{
               prev=cur;
               cur=cur.right;
           }
       }
       if(cur==null) return false;
       if(cur.left==null){
         if(cur==root){
             cur=cur.right;
         }else if(prev.left==cur){
             prev.left=cur.right;
         }else{
             prev.right=cur.right;
         }
       }else if(cur.right==null){
           if(cur==root){
               cur=cur.left;
           }else if(prev.left==cur){
               prev.left=cur.left;
           }else{
               prev.right=cur.left;
           }
       }else{
           //从左树种找最大的节点或者从右树中找最小的节点进行替换，替换后删除找到的节点
           TreeNode target=cur.right;
           TreeNode parent=cur;
           while(target.left!=null){
               parent=target;
               target=target.left;
           }
           cur.val=target.val;
           if(target==parent.right){
               parent.right=target.right;
           }else{
              parent.left=target.right;
           }
       }
        return true;
    }
    public void display(){
         display(this.root);
    }
    public void display(TreeNode root){
        if(root==null) return;
        display(root.left);
        System.out.println(root.val);
        display(root.right);
    }
   
}
 